◀ Prev · Parts · Full · Next ▶

1. Given a fragment of an MST T {\displaystyle T} , let e {\displaystyle e} be a minimum-weight outgoing edge of the fragment. Then joining e {\displaystyle e} and its adjacent non-fragment node to the fragment yields another fragment of an MST.

2. If all the edges of a connected graph have different weights, then the MST of the graph is unique.

These two properties form the basis for proving correctness of the GHS algorithm. In general, the GHS algorithm is a bottom-up algorithm in the sense that it starts by letting each individual node be a fragment, and then joining fragments until a single fragment is left. The above properties imply that the remaining fragment must be an MST.

The GHS algorithm assigns a level to each fragment, which is a non-decreasing integer with initial value 0. Furthermore, each fragment with a non-zero level has an ID, which is the ID of the core edge in the fragment, which is selected when the fragment is constructed. During the execution of the algorithm, each node can classify each of its incident edges into three categories:cite-ref-ghs-1-3[1]cite-ref-lynch-6-0[6]

• Branch edges are those that have been determined to be part of the MST.

• Rejected edges are those that have been determined not to be part of the MST.

• Basic edges are all edges that are neither branch edges nor rejected edges.

In level-0 fragments, each awakened node will do the following:

1. Choose its minimum-weight incident edge and mark that edge as a branch edge.

2. Send a message via the branch edge to notify the node on the other side.

3. Wait for a message from the other end of the edge.

The edge that is chosen by the two nodes it connects becomes the core edge, and is assigned level 1.

In non-zero-level fragments, a separate algorithm is executed in each level. This algorithm can be separated into three stages: broadcast, convergecast, and change core.

◀ Prev · Parts · Full · Next ▶